A smart card C with a chip or chips comprises a microcircuit MC shown in FIG. 1, essentially comprising an input-output interface, a microprocessor UC, an operating program memory M1 for example a ROM (or “Read Only Memory”), an application(s) program memory M3 for example an EEPROM (“Electrically Erasable Programmable Read Only Memory”), a working memory M2, for example a RAM (“Random Access Memory”).
In the case of contact-type smart cards, the input-output interface is formed by an asynchronous reception or transmission unit UART and a receiver CN generally comprising eight contact zones flush with the card.
In the case of contactless smart cards, this input/output interface is formed by the asynchronous unit UART and a radiofrequency transmitter-receiver device RF comprising an antenna.
In the case of combined-operation smart cards, this interface comprises, of course, the device RF and the contact zones CN.
The field of the invention is that of smart cards using the results of exponentiation computations referenced gx and often done as modulo n computations. These computations are executed in numerous applications based especially on the signing or authentication of messages.
The most practical and reliable authentication or signing schemes used at present are the public key algorithms. The best-known and most widely used of these is the RSA algorithm (named after its inventors R. Rivest, A. Shamir and L. Adleman), which is costly in computation time. The schemes based on the discrete algorithm too have been known for a long time and have the advantage of lending themselves to precomputation operations relating especially to the exponentiation computations which are very costly in time.
The invention can be applied to microcircuit cards implementing public key algorithms using the discrete logarithm in any mathematical structure, especially rings of numbers modulo n (where n belongs to the set Zn, the set of positive integers smaller than n), the elliptic curves on the finite fields GF(q) (GF(q) being the field for which the number of elements is q, with q as a prime number or the power of a prime number). The exponentiation gx covers all these structures.
Exemplary methods implementing such computations are presented in the patent application FR No. FR 2 716 058.
In the case of Zn and of the present embodiments requiring modular exponentiation type (bx modulo n) computations where the numbers b, x and n commonly have lengths ranging from 768 to 1024 bits, the performances are in the range of 500 to 300 ms. This performance can be achieved only with 8-bit microprocessors using “crypto-processors” capable of performing high-speed operations of multiplication and modulo n reduction or with 16-bit or 32-bit microprocessors whose intrinsic performance characteristics enable these performance levels to be achieved without resorting to a specific computation cell such as a crypto-processor.
These performance levels are not sufficient in certain cases. We shall now present an exemplary use of combination cards for public transport services.
When the card works in contactless mode, it must enable a terminal, during entry into an underground station or into a bus, to authenticate the ticket, verify an entitlement to a certain type of reduction and/or receive payment by electronic wallet (PME). For this type of transaction, as in general for PME type transactions, the public key cryptography algorithms are used for purposes of key management, compliance with standards and, ultimately, security.
This type of transaction must take place within 150 ms. This is the time needed for a user to pass the card, in a natural movement, before a terminal integrated into a turnstile or located at the entrance to a bus. These 150 ms must then cover not only the cryptographic computations but also the inputs/outputs of the messages and the processing operations other than cryptographic processing operations, whether they are done on the terminal side or on the card side. The processing operations on the terminal side and card side cannot take place in parallel because they are sequenced in a precise order established by a predefined protocol. In practice, given the computation time required on the terminal side, the cryptographic computations on the card side must therefore take place in less than 30 ms.
There is no microcircuit card component today that enables such performance levels to be achieved. Furthermore, since the card, in contactless mode, is powered by the energy radiated by the terminal and recovered at the antenna, the consumable power is limited and therefore the computation capacities are limited too.
In contact mode, these constraints are not as acute. For example, in payment by electronic purse or wallet, the customer does not need to be made to wait at the sales point for more than a few seconds. However, certain operations demand that the transactions should remain short, in the range of one second.
To know the details of the computations performed by a public key cryptography algorithm, reference may be made to the patent application FR No. 2 716 058 which presents a method for the digital signing and authentication of messages using a discrete logarithm.
The method as described in the above patent may be summarized as follows.
The signing method is preceded by a preliminary phase shown in FIG. 2a. 
An authority A, for example a bank or a transport organization, holding a public key PA and a secret signing key SA, chooses a number n (a prime number or composite of prime numbers) and g (an integer smaller than n and generally far smaller) as well as a hashing function h and sends PA, n, g and h to the entity S which must sign a message, this entity being for example a smart card that has to validate an amount to be paid, as well as to the entities V which must verify the signing, these entities being, for example, terminals such as the ones presently used by tradesmen with their customers.
The entity S chooses a secret key x, computes its public key y=g−x mod n, sends it to the authority A which sends back a certificate Cert to it. This certificate is itself set up especially on the basis of its secret signing key SA.
The pieces of data n, g, x, y, Cert are permanent data of the entity S.
With this preliminary phase completed, the method for signing a message M can start. For S, as shown in FIG. 2b, this may entail the signing of an amount to be paid proposed by V; the message M contains especially the amount to be paid m and an identification of the terminal V requesting this payment.
The following are the steps of this signing method:                a) S randomly chooses k,        b) a witness element r=gk mod n is computed        c) a known hashing function h of A, S and V is used to compute c=h(r,M)        d) finally s=k+cx is computed        e) S sends V this information: y, Cert, M, c, S        V verifies Cert with PA, computes u=ycgs mod n and verifies that c=h(u,M). If the verification is right, the signing of M is authenticated.        
One of the steps of this method consists of the computation, at each transaction, of a witness r requiring an exponentiation (r=gk mod n for example). This operation uses a great deal of time; this is why it is sometimes planned to precompute these witness elements. However, these precomputations are done by an external device and then the pairs (k,r) are written in a storage zone of the card, for example M3, and this has drawbacks.
Indeed, the knowledge of the data needed to compute these witness elements and knowledge of the witness elements themselves makes it possible to recover the secret cryptography key. Indeed, the knowledge of r and k gives c=h(r,M); the knowledge of s=k+cx and k and c and gives x. The secret is therefore shared between the entity supposed to hold it and this external device in which therefore a great deal of trust has to be placed.
It is also necessary to be assured of the total security of the sending of the pairs (k,r) to the card and of their writing.
Furthermore, if the card no longer contains pairs (k,r), it must be reloaded with them. This requires a special terminal connected to a network.